

public class RBTree {
    static class RBTreeNode {
        public int val;
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public COLOR color = COLOR.RED;

        public RBTreeNode(int val) {
            this.val = val;
        }
    }

    RBTreeNode root;

    public void insert(int val) {
        RBTreeNode node = new RBTreeNode(val);
        if (root == null) {
            root = node;
            node.color = COLOR.BLACK;
            return;
        }
        RBTreeNode parent = null;
        RBTreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                System.out.println("节点已存在");
                return;
            }
        }
        if (parent.val > val) {
            parent.left = node;
            cur = node;
            cur.parent = parent;
        } else {
            parent.right = node;
            cur = node;
            cur.parent = parent;
        }

        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandParent = parent.parent;
            if (grandParent.left == parent) {
                RBTreeNode uncle = grandParent.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    uncle.color = COLOR.BLACK;
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                    cur = grandParent;
                    parent = cur.parent;
                } else {
                    if(parent.right == cur) {
                        rotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    rotateRight(grandParent);
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            } else {
                //grandParent.right == parent

            }
        }
    }

    public void rotateRight(RBTreeNode parent) {
        RBTreeNode subL = parent.left;
        RBTreeNode subLR = subL.right;
        parent.left = subLR;
        if(subLR != null) {
            subLR.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        parent.parent = subL;
        subL.right = parent;
        if(root == parent) {
            root = subL;
            subL.parent = null;
            return;
        }
        if(pParent.left == parent) {
            pParent.left = subL;
        }else {
            pParent.right = subL;
        }
        subL.parent = pParent;;
    }

    public void rotateLeft(RBTreeNode parent) {
        RBTreeNode subR = parent.right;
        RBTreeNode subRL = subR.left;
        parent.left = subRL;
        if(subRL != null) {
            subRL.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        subR.left = parent;
        parent.parent = subR;
        if(root == parent) {
            subR.parent = null;
            root = subR;
            return;
        }
        if(pParent.left == parent) {
            pParent.left = subR;
        }else{
            pParent.right = subR;
        }
        subR.parent = pParent;
    }
}
